package cn.handong.tool.algorithm.二叉树;

import sun.reflect.generics.tree.Tree;

import javax.persistence.criteria.CriteriaBuilder;
import java.util.*;

public class 遍历 {

    // 层序遍历
    public List<List<Integer>> levelOrder1(TreeNode root){
        if (root == null){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Integer num;
        while (!queue.isEmpty()){
            num = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < num; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }

    public List<List<Integer>> levelOrder(TreeNode root){
        if (root == null){
            return null;
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Boolean flag = true;
        while (queue.size() > 0){
            Integer size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            if (flag){
                Collections.reverse(temp);
            }
            flag = !flag;
        }
        return res;
    }


    public Integer getMaxDepth(TreeNode root){
        return root == null ? 0 : Math.max(getMaxDepth(root.left),getMaxDepth(root.right))+1;
    }

    ///////////////////////////////////////////////////////
    HashMap<Integer,Integer> map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留先序遍历，方便递归时查找
    public TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return recur(0,0,inorder.length - 1);
    }

    private TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left > in_right){
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre_root]); //获取root节点
        Integer idx = map.get(root.val); //获取中序遍历中该节点的索引位置
        root.left = recur(pre_root + 1,in_left,idx - 1);
        root.right = recur(pre_root + (idx - in_left) + 1,idx + 1,in_right);
        return root;
    }



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A,TreeNode B){
        if (root == null){
            return null;
        }
        if (root == A || root == B){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null){
            return root;
        }
        if (left != null){
            return left;
        }
        if (right != null){
            return right;
        }
        return null;
    }

}
